{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f283e47-1605-447c-9fd9-ac35f30111e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install numpy scikit-learn matplotlib"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c35589a-3430-48b5-9ccb-115fcfabbac1",
   "metadata": {},
   "source": [
    "# Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0b32c8f1-3fd6-4796-b38b-96ace74c297f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import accuracy_score"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7685d9c1-86e9-47cc-ada4-836cf43de0d2",
   "metadata": {},
   "source": [
    "# Load and Preprocess Iris Dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c87a4ab8-4c0b-4c65-8c08-c5aeff6e5f0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "iris = load_iris()\n",
    "X, y = iris.data, iris.target\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    X, y, test_size=0.1, stratify=y, random_state=42\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63df4860-bc90-459a-be53-f0c9357d8731",
   "metadata": {},
   "source": [
    "# Gini Impurity\n",
    "\n",
    "Gini impurity measures the chance of misclassifying a random sample if it were labeled according to the class proportions in a node. It’s calculated as \n",
    "\n",
    "$$ 1 - \\sum_i p_i^2 $$\n",
    "\n",
    "where $p_i$ is the fraction of samples in class $i$. Lower values mean purer nodes (0 = all samples in one class)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac8ae7c6-8f13-4e39-8bbe-9bf53ca53d70",
   "metadata": {},
   "source": [
    "# Decision Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cfffbdf9-ac79-46f1-8832-995bc8dbdef2",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTreeScratch:\n",
    "    def __init__(self, max_depth=None):\n",
    "        self.max_depth = max_depth\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        self.tree = self._build(X, y, 0)\n",
    "\n",
    "    def _gini(self, y):\n",
    "        # Your code is here\n",
    "\n",
    "    def _best_split(self, X, y):\n",
    "        best = {\"feat\": None, \"thr\": None, \"score\": float(\"inf\")}\n",
    "        for feat in range(X.shape[1]):\n",
    "            for thr in np.unique(X[:, feat]):\n",
    "                left = y[X[:, feat] <= thr]\n",
    "                right = y[X[:, feat] > thr]\n",
    "                if len(left)==0 or len(right)==0: continue\n",
    "                g = (self._gini(left)*len(left) + self._gini(right)*len(right)) / len(y)\n",
    "                if g < best[\"score\"]:\n",
    "                    best.update(feat=feat, thr=thr, score=g)\n",
    "        return best\n",
    "\n",
    "    def _build(self, X, y, depth):\n",
    "        if len(np.unique(y)) == 1 or (self.max_depth and depth == self.max_depth):\n",
    "            return {\"leaf\": True, \"value\": np.bincount(y).argmax()}\n",
    "        split = self._best_split(X, y)\n",
    "        if split[\"feat\"] is None:\n",
    "            return {\"leaf\": True, \"value\": np.bincount(y).argmax()}\n",
    "        mask = X[:, split[\"feat\"]] <= split[\"thr\"]\n",
    "        return {\n",
    "            \"leaf\": False,\n",
    "            \"feat\": split[\"feat\"],\n",
    "            \"thr\": split[\"thr\"],\n",
    "            \"left\": self._build(X[mask], y[mask], depth+1),\n",
    "            \"right\": self._build(X[~mask], y[~mask], depth+1),\n",
    "        }\n",
    "\n",
    "    def predict(self, X):\n",
    "        return np.array([self._predict_one(x, self.tree) for x in X])\n",
    "\n",
    "    def _predict_one(self, x, node):\n",
    "        if node[\"leaf\"]:\n",
    "            return node[\"value\"]\n",
    "        branch = node[\"left\"] if x[node[\"feat\"]] <= node[\"thr\"] else node[\"right\"]\n",
    "        return self._predict_one(x, branch)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ecb6661-884f-456d-a8c4-e1f872832793",
   "metadata": {},
   "source": [
    "# Train and Evaluate Decision Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a1ec6aa-1b0d-42ab-aeab-2dad1a8cfb4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "dt = DecisionTreeScratch(max_depth=3)\n",
    "dt.fit(X_train, y_train)\n",
    "print(\"Scratch DT accuracy:\", accuracy_score(y_test, dt.predict(X_test)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "606cb3d6-90c8-404e-8227-bd1e8187109d",
   "metadata": {},
   "source": [
    "# Random Forest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6370fb8a-4001-43d5-8cda-7fc5a3ad9a24",
   "metadata": {},
   "outputs": [],
   "source": [
    "class RandomForestScratch:\n",
    "    def __init__(self, n_estimators=10, max_depth=None):\n",
    "        self.n_estimators = n_estimators\n",
    "        self.max_depth = max_depth\n",
    "        self.trees = []\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        n = len(X)\n",
    "        for _ in range(self.n_estimators):\n",
    "            idx = np.random.choice(n, n, replace=True)\n",
    "            tree = DecisionTreeScratch(max_depth=self.max_depth)\n",
    "            tree.fit(X[idx], y[idx])\n",
    "            self.trees.append(tree)\n",
    "\n",
    "    def predict(self, X):\n",
    "        preds = np.array([tree.predict(X) for tree in self.trees])\n",
    "        return np.apply_along_axis(lambda row: np.bincount(row).argmax(), axis=0, arr=preds)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05ed733f-61ae-46bb-a591-0013fb7b9c6e",
   "metadata": {},
   "source": [
    "# Train and Evaluate Random Forest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "756121ba-8bc9-4064-ac19-dc0918dbefb0",
   "metadata": {},
   "outputs": [],
   "source": [
    "rf = RandomForestScratch(n_estimators=10, max_depth=3)\n",
    "rf.fit(X_train, y_train)\n",
    "print(\"Scratch RF accuracy:\", accuracy_score(y_test, rf.predict(X_test)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7b1ac216-99df-4a8d-a04e-06153b88ba65",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}